/*
day478 
2020.12.18 
*/

#include<iostream>
#include<vector>
using namespace std;

 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
		int size=len(head);
		int half=size/2;
		ListNode *head2=head;
		
		for(int i=1;i<half;++i)
		{
			head2=head2->next;
		}
		
		if(size%2==1) head2=head2->next;
		
		ListNode *p=head2->next,*r;
		while(p)
		{
			r=p->next;
			p->next=head2->next;
			head2->next=p;
			p=r;
		 } 
		 
		ListNode *p1=head,*p2=head2;
		while(p1 && p2)
		{
			if(p1->val != p2->val)
			{
				return false;
			}
			p1=p1->next;
			p2=p2->next; 
		}
		
		return true;
    }
    
    int len(ListNode* head)
	{
		int sum=0;
		while(head)
		{
			sum++;
			head=head->next;
		}
		
		return sum;
	 } 
};

int main()
{
	return 0;
 } 
